\section{Problem 2}

	\subsection*{Question a}
	
		The number of vertices in a B-tree of depth $d$ corresponds to the following parametrized summation :
		\begin{displaymath}
				n_v  =  1 + \sum_{i = 0}^{d-1}(m+1)(r+1)^{i}
		\end{displaymath}
		where $n_v$ is the number of vertices, $m$ the number of records in the root vertex, $r$ the number of records in other vertices. 
		
		By factoring $m+1$ the formula becomes :
		\begin{displaymath}
				n_v(d)  =  1 + (m+1)\sum_{i = 0}^{d-1}(r+1)^{i}
		\end{displaymath}
		
		That transformation makes appear a geometric series of common ratio $r+1$. Then, by using the geometric sum, we obtain the following closed formula :
		\begin{equation}
			n_v(d) = 1 + (m+1)\dfrac{1 - (r + 1)^{d}}{1-(r+1)}
			\label{eq:nbvertclosed}
		\end{equation}
		
	\subsection*{Question b}
	
		From the equation \ref{eq:nbvertclosed}, we have the following equation :
		\begin{equation}
			n_v(i_{mem} - 1)\times pageSize = (1 + (m+1)\dfrac{1 - (r + 1)^{i_{mem}-1}}{1-(r+1)}) \times pageSize \leq memorySize
		\end{equation}
		Which leads to : 
		\begin{equation}
			i_{mem} -1 \leq \dfrac{ln\left(\dfrac{r(memorySize - pageSize)}{pageSize(m+1)} + 1\right)}{ln(r + 1)}
			\label{eq:imem}
		\end{equation}
		Numerical application :
		\begin{displaymath}
			\begin{array}{r c l}
				i_{mem} & \leq & \dfrac{ln\left(\dfrac{12,59(2^{33} - 8192)}{8192(1+1)} + 1\right)}{ln(12,59 + 1)} + 1\\
				&&\\
				i_{mem} & \leq & 7,017894644
			\end{array}
		\end{displaymath}
		As $i_{mem}$ is an integer, $i_{mem} = 7 \Leftrightarrow i_{mem} - 1 = 6$
		
	\subsection*{Question c}		
	
	The found parameters in 1.c are : 
	\begin{displaymath}
		\left\lbrace 
			\begin{array}{r c l}
			d&=d_{max}&=9\\
			r&=12.51&\\
			m&=1&\\
			\end{array}\right.
	\end{displaymath}
	
	As $i_{mem}$ is equal to 7, the first six levels are cached. Thus the disk access are only required from level $i_{mem}$ to $d$, which means only for $9 - 6 = 3$ levels.
	
	The number of disk accesses is equal to the number of pointers to be chased. Since some vertices on level $i_{mem}$ might be cached, the number of disk accesses lays between $2$ and $3$.
	
	The probability that a vertex on level $i_{mem}$ is not cached is given by the following :
	\begin{equation}
		P = 1 - \dfrac{n_c}{n_{v_7}} = 1 - \dfrac{\left(\dfrac{memorySize}{pageSize} - n_v(6)\right)}{(m + 1) \times (r + 1)^{6}}
	\end{equation}
	Which leads to :
	\begin{displaymath}
		\begin{array}{r c l}
			n_{v_7}&=& (1 + 1)\times(12.51 + 1)^{6}\\
			&=& 12160798.426157191\\
			n_c &=& \dfrac{2^{33}}{8192} - 900133.97\\
			&=&148442.02989214\\
			P&=&1 - \dfrac{148442.02}{12160798.42}\\
			&=&1 - 0.012206602\\
			&=& 0.987793398
		\end{array}
	\end{displaymath}
	The average number of disk accesses required in order to find a leaf record in then $2 + 0.987793398 \simeq 2.99$.
	\subsection*{Question d}
	
	Let compute the equation \ref{eq:imem} with the arguments found in 1.e : 
	\begin{displaymath}
			\begin{array}{r c l}
				i_{mem} & \leq & \dfrac{ln\left(\dfrac{19,18(2^{33} - 8192)}{8192(21+1)} + 1\right)}{ln(19,18 + 1)} + 1\\
				&&\\
				i_{mem} & \leq & 5,568111906
			\end{array}
		\end{displaymath}
		As $i_{mem}$ is an integer, $i_{mem} = 5 \Leftrightarrow i_{mem} - 1 = 4$
		
	\subsection*{Question e}
			
			Following the same reflexion that in 2.c, with the parameters found in 1.e : 
	\begin{displaymath}
		\left\lbrace 
			\begin{array}{r c l}
			d&=d_{min}&=7\\
			r&=19.18&\\
			m&=21&\\
			\end{array}\right.
	\end{displaymath}
	
	and $i_{mem} = 5$, we find that the number of disk accesses is also between $2$ and $3$.
	
	The probability for a vertex in level $5$ being cached is then : 
		\begin{equation}
		P = 1 - \dfrac{n_c}{n_{v_5}}
	\end{equation}
	Which leads to :
	\begin{displaymath}
		\begin{array}{r c l}
			n_{v_5}&=& (21 + 1)\times(19.18 + 1)^{4}\\
			&=& 3648441.00741472\\
			n_c &=& \dfrac{2^{33}}{8192} - 190220.96\\
			&=&858355.030896\\
			&&\\
			P&=&1 - \dfrac{858355.03}{3648441.01}\\
			&=&1 - 0.235266249\\
			&=&0.764733751
		\end{array}
	\end{displaymath}
	The average number of disk accesses required in order to find a leaf record in then $2 + 0.764733751 = 2.764733751 \simeq 2.76$.